package nowcoder;

public class MergeList {

	public static void main(String[] args) {

	}

	public ListNode merge(ListNode list1,ListNode list2) {
		if(list1 == null)
			return list2;
		if(list2 == null)
			return list1;
		ListNode p1 = list1, p2 = list2, newHead, current;
		if(p1.val <= p2.val) {
			newHead = p1;
			p1 = p1.next;
		}else {
			newHead = p2;
			p2 = p2.next;
		}
		current = newHead;
		while(p1 != null && p2 != null) {
			if(p1.val <= p2.val) {
				current.next = p1;
				p1 = p1.next;
			}else {
				current.next = p2;
				p2 = p2.next;
			}
			current = current.next;
		}
		
		if(p1 != null)
			current.next = p1;
		
		if(p2 != null)
			current.next = p2;
		
		return newHead;
	}

}
